class Solution(object):
    class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n==0:
            return []
        # dp[begin][end][pivot]
        dp = [[[] for _ in range(n+1)] for _ in range(n+1)]
        for begin in range(n+1):
            for end in range(n+1):
                if begin>=end:
                    dp[begin][end].append(None)
        for i in range(n):
            dp[i][i+1].append(TreeNode(i+1))
        for stride in range(2, n+1):
            for begin in range(0, n+1-stride):
                end=begin+stride
                for pivot in range(begin, end):
                    for left in dp[begin][pivot]:
                        for right in dp[pivot+1][end]:
                            node = TreeNode(pivot+1)
                            node.left = left
                            node.right = right
                            dp[begin][end].append(node)
        return dp[0][n]

print(Solution().generateTrees(0))
                    
                    